home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / BOOL2LOW.C < prev    next >
C/C++ Source or Header  |  1991-11-10  |  38KB  |  964 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see Irit.h)!             *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersecting polyline between the oprnds.  *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. *****************************************************************************/
  18.  
  19. /* #define DEBUG        If defined, return intersection POLYLINE object. */
  20. /* #define DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #ifdef __MSDOS__
  24. #include <alloc.h>
  25. #include <dos.h>
  26. #endif /* __MSDOS__ */
  27.  
  28. #include <stdio.h>
  29. #include <ctype.h>
  30. #include <math.h>
  31. #include <string.h>
  32. #include "program.h"
  33. #include "allocate.h"
  34. #include "booleang.h"
  35. #include "booleanl.h"
  36. #include "convex.h"
  37. #include "geomat3d.h"
  38. #include "intrnrml.h"
  39. #include "objects.h"
  40.  
  41. static int TestAinB(VertexStruct *V, PolygonStruct *Pl, int AinB);
  42. static PolygonStruct *ClipOpenLoopFromPoly(PolygonStruct *Pl,
  43.                     InterSegListStruct *OLoop, int AinB);
  44. static void ClosedLoopsToPolys(InterSegListStruct *PClosed, PolygonStruct *Pl);
  45. static VertexStruct *CutPolygonAtRay(PolygonStruct *Pl, PointType Pt);
  46. static CombineClosedLoops(PolygonStruct *Pl, InterSegListStruct *PClosed,
  47.                                 int AinB);
  48. static void PushAdjOnStack(PolygonStruct *Pl, PolygonStruct *AdjStack[],
  49.                              int *StackPointer);
  50. static PolygonStruct *ChainPolyLists(PolygonStruct *Pl1, PolygonStruct *Pl2);
  51.  
  52. #ifdef DEBUG2
  53. static void PrintVrtxList(VertexStruct *V);
  54. static void PrintInterList(InterSegmentStruct *PInt);
  55. #endif /* DEBUG2 */
  56.  
  57. /*****************************************************************************
  58. *   Test on which side of polygon Pl, given Point V is, and according to     *
  59. * the requirement (AinB) returns TRUE/FALSE.                     *
  60. *   If test on V fails, we tries the next one V -> Pnext until success...    *
  61. *****************************************************************************/
  62. static int TestAinB(VertexStruct *V, PolygonStruct *Pl, int AinB)
  63. {
  64.     int In;
  65.     RealType Distance;
  66.     VertexStruct *VHead = V;
  67.  
  68.     do {
  69.     Distance = Pl -> Plane[0] * V -> Pt[0] +
  70.            Pl -> Plane[1] * V -> Pt[1] +
  71.            Pl -> Plane[2] * V -> Pt[2] + Pl -> Plane[3];
  72.     In = Distance > 0.0;
  73.     V = V -> Pnext;
  74.     }
  75.     while (ABS(Distance) < EPSILON && V != NULL && V != VHead);
  76.  
  77.     if (ABS(Distance) < EPSILON)
  78.     FatalError("TestAInB: Failed to find non coplanar point.\n");
  79.  
  80.     return (In && AinB) || (!In && !AinB);   /* I wish I had logical XOR ... */
  81. }
  82.  
  83. /*****************************************************************************
  84. *   Convert an inter loop into an open vertex list.                 *
  85. *****************************************************************************/
  86. VertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead)
  87. {
  88.     VertexStruct *VHead, *V;
  89.  
  90.     VHead = V = AllocVertex(0, 0, NULL, NULL);
  91.  
  92.     PT_COPY(VHead -> Pt, PIHead -> PtSeg[0]);
  93.  
  94.     while (PIHead != NULL) {
  95.     V -> Pnext = AllocVertex(0, 0, NULL, NULL);
  96.     V = V -> Pnext;
  97.     PT_COPY(V -> Pt, PIHead -> PtSeg[1]);
  98.  
  99.     PIHead = PIHead -> Pnext;
  100.     }
  101.  
  102.     V -> Pnext = NULL;
  103.  
  104.     return VHead;
  105. }
  106.  
  107. /*****************************************************************************
  108. *   Clip an open loop from a polygon:                         *
  109. * 1. Clip the section (S) of the polygon between the two loop end points and *
  110. *    replace it by the loop itself.                         *
  111. * 2. If the polygon formed from S and the loop should be in the output       *
  112. *    (as tested by AinB) return that polygon. Otherwise return NULL.         *
  113. *   The open loop itself (excluding the header OLoop) is freed.             *
  114. * Note it is assumed (ordered by the sorting routines above) that the open   *
  115. * loop starts from the second end back to first:                 *
  116. *                                         *
  117. *                   L1-----------------------L2             *
  118. *                |            |             *
  119. *                |L0            |L3             *
  120. *    *---------------*-------+----*-------------*----+-----------*         *
  121. *    P0        P1         P2           P3            P0         *
  122. *****************************************************************************/
  123. static PolygonStruct *ClipOpenLoopFromPoly(PolygonStruct *Pl,
  124.                     InterSegListStruct *OLoop, int AinB)
  125. {
  126.     int GenClipPoly;        /* TRUE if needs to form polygon from S & OLoop. */
  127.     VertexStruct *VStart,  *VEnd, *VEnd1,     /* Corresponds to L0 and L3... */
  128.          *ClipPoly,        /* The clipped element from polygon. */
  129.          *PLoop, *PRevLoop,      /* The loop itself as vertex list. */
  130.          *PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2;
  131.     InterSegmentStruct *PISeg, *PItemp;
  132.     PolygonStruct *ClipPl;
  133.  
  134. #ifdef DEBUG3
  135.     printf("Enter ClipOpenLoopFromPoly\n");
  136. #endif /* DEBUG3 */
  137.  
  138.     PISeg = OLoop -> PISeg;
  139.     VStart = PISeg -> V[0];
  140.     while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext;
  141.     VEnd = PISeg -> V[1];
  142.     if (VStart == NULL || VEnd == NULL)
  143.     FatalError("ClipOpenLoopFromPoly: None open loop\n");
  144.     VEnd1 = VEnd;           /* Find the pointer thats points on VEnd. */
  145.     while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext;
  146.  
  147.     PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/
  148.     PLoopEnd = PLoop;              /* Prepare pointer on last vertex. */
  149.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  150.     PLoopEnd1 = PLoop;
  151.     while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext;
  152.  
  153.     if (VStart != VEnd) {
  154.     /* Now we test if we need to create a polygon formed from S & open   */
  155.     /* loop by testing on which side of the polygon that caused         */
  156.     /* intersection L0L1, point P2 is, and compare with requirement AinB.*/
  157.     GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB);
  158.  
  159.     /* Keep the clipped VertexList P2, P3 & substitute with open loop:   */
  160.     /* Note we must keep vertex VEnd in the polygon as another InterSeg. */
  161.     /* may point on it, so we replace InterSeg point (L3) by (P3) and    */
  162.     /* leave VEnd intact.                             */
  163.     Ptemp1 = VEnd -> Pnext;             /* Save that pointer temporary. */
  164.     VEnd -> Pnext = NULL;           /* Close the clipped vertex list. */
  165.  
  166.     PT_SWAP(VEnd -> Pt, PLoopEnd -> Pt);
  167.     PT_SWAP(VEnd -> Normal, PLoopEnd -> Normal);
  168.     VEnd1 -> Pnext = PLoopEnd;
  169.     PLoopEnd1 -> Pnext = VEnd;
  170.     PLoopEnd -> Count = VEnd -> Count;
  171.     PLoopEnd -> Tags = VEnd -> Tags;
  172.  
  173.     Ptemp2 = VEnd;
  174.     VEnd = PLoopEnd;
  175.     PLoopEnd = Ptemp2;
  176.  
  177.     ClipPoly = VStart -> Pnext;
  178.  
  179.     /* New ClipPoly is isolated (Open loop of P2, P3 only). Save         */
  180.     /* reversed list of open loop if we need to form an S/OLoop polygon, */
  181.     /* otherwise free ClipPoly. Chain the OLoop instead of S.         */
  182.     if (GenClipPoly)
  183.         PRevLoop = GenReverseVrtxList(PLoop);
  184.     else
  185.         MyFree((char *) ClipPoly, ALLOC_VERTEX);
  186.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  187.     PLoopEnd -> Pnext = Ptemp1;
  188.     }
  189.     else { /* VStart == VEnd */
  190.     /* Now we test if we need to create a polygon formed from S & open   */
  191.     /* loop by testing on which side of the polygon that caused         */
  192.     /* intersection L0L1, point L3 is, and compare with requirement AinB.*/
  193.     GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB);
  194.  
  195.     /* In this case the clipped part is empty, so its simpler: */
  196.     ClipPoly = NULL;
  197.  
  198.     /* Save reversed list of open loop if we need to form an S/OLoop     */
  199.     /* polygon. Chain the OLoop instead of S.                 */
  200.     if (GenClipPoly) PRevLoop = GenReverseVrtxList(PLoop);
  201.  
  202.     PLoopEnd -> Pnext = VEnd -> Pnext;
  203.     PLoopEnd -> Tags = VEnd -> Tags;
  204.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  205.     }
  206.  
  207.     /* Time to free the InterSegment list pointed by OLoop: */
  208.     PISeg = OLoop -> PISeg;
  209.     while (PISeg != NULL) {
  210.     PItemp = PISeg;
  211.     PISeg = PISeg -> Pnext;
  212.     MyFree((char *) PItemp, ALLOC_OTHER);
  213.     }
  214.     OLoop -> PISeg = NULL;            /* To be on the safe side... */
  215.  
  216.     /* There is a chance that Pl -> V will point on vertex in the clipped    */
  217.     /* part so we update it to point on VStart, which for sure is in polygon.*/
  218.     Pl -> V = VStart;
  219.     if (GenClipPoly) {       /* Generate the polygon from ClipPoly & PRevLoop: */
  220.     PLoopEnd = PRevLoop;
  221.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  222.  
  223.     if (ClipPoly == NULL) {
  224.         PLoopEnd -> Pnext = PRevLoop;  /* Close that loop and return it. */
  225.         ClipPl = AllocPolygon(0, 0, PRevLoop, NULL);
  226.         PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  227.         RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  228.         return ClipPl;
  229.     }
  230.  
  231.     PLoopEnd -> Pnext = ClipPoly;
  232.     PLoopEnd -> Tags = VStart -> Tags;
  233.     PLoopEnd -> Count = VStart -> Count;
  234.     Ptemp1 = ClipPoly;
  235.     while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext;
  236.     Ptemp1 -> Pnext = PRevLoop;
  237.  
  238.     ClipPl = AllocPolygon(0, 0, ClipPoly, NULL);
  239.     PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  240.     RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  241.     return ClipPl;
  242.     }
  243.     else
  244.     return NULL;
  245. }
  246.  
  247. /*****************************************************************************
  248. * Find the intersection of the ray fired from Pt to +X direction with the    *
  249. * given polygon. Note Pt MUST be in the polygon. Two vertices equal to         *
  250. * ray/polygon intersection point are added to polygon vertex list, and a     *
  251. * pointer to the first one is also returned. This routine is exclusively     *
  252. * used by the CombineClosedLoops below.                         *
  253. * The polygon is NOT assumed to be convex and we look for the minimum X      *
  254. * intersection. The polygon might not be convex as a result of combinning    *
  255. * some other closed loop before the current one...                 *
  256. *****************************************************************************/
  257. static VertexStruct *CutPolygonAtRay(PolygonStruct *Pl, PointType Pt)
  258. {
  259.     int OnVertex;
  260.     RealType MinX = INFINITY, X;
  261.     VertexStruct *V, *Vnext, *VMinX = NULL;
  262.  
  263.     V = Pl -> V;
  264.     do {
  265.     Vnext = V -> Pnext;
  266.  
  267.     /* A polygon edge might intersect the ray iff one of the following:  */
  268.     /* 1. The first vertex is exactly on the ray Y level. (if this is    */
  269.     /*    true for the second edge, it will be detected next iteration). */
  270.     /* 2. The first vertex is below ray Y level, and second is above.    */
  271.     /* 3. The first vertex is above ray Y level, and second is below.    */
  272.     if (APX_EQ(V -> Pt[1], Pt[1])) {            /* Case 1 above. */
  273.         if (MinX > V -> Pt[0] && Pt[0] < V -> Pt[0]) {
  274.         OnVertex = TRUE;
  275.         MinX = V -> Pt[0];
  276.         VMinX = V;
  277.         }
  278.     }
  279.     else if ((V -> Pt[1] < Pt[1] && Vnext -> Pt[1] > Pt[1]) ||/* Case 2. */
  280.          (V -> Pt[1] > Pt[1] && Vnext -> Pt[1] < Pt[1])) {/* Case 3. */
  281.         X = ((Vnext -> Pt[1] - Pt[1]) * V -> Pt[0] +
  282.          (Pt[1] - V -> Pt[1]) * Vnext -> Pt[0]) /
  283.         (Vnext -> Pt[1] - V -> Pt[1]);
  284.         if (MinX > X && Pt[0] < X) {
  285.         OnVertex = FALSE;
  286.         MinX = X;
  287.         VMinX = V;
  288.         }
  289.  
  290.     }
  291.  
  292.     V = Vnext;
  293.     }
  294.     while (V != NULL && V != Pl -> V);
  295.  
  296.     if ((V = VMinX) == NULL)
  297.     FatalError("CutPolygonAtRay: fail to find intersection");
  298.  
  299.     /* Now that we have the intersection point - create two new vertices     */
  300.     /* (one if OnVertex), insert them (it) after V and return the first.     */
  301.     if (OnVertex) {
  302.     V -> Pnext = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  303.     PT_COPY(V -> Pnext -> Pt, V -> Pt);
  304.     PT_CLEAR(V -> Pnext -> Normal);
  305.     V -> Tags = V -> Count = 0;
  306.     }
  307.     else {
  308.     V -> Pnext = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  309.     Vnext = V -> Pnext;
  310.     Vnext -> Pt[0] = MinX;         /* X - as intersection point found. */
  311.     Vnext -> Pt[1] = Pt[1];              /* Y - must be as ray Y level. */
  312.     Vnext -> Pt[2] = V -> Pt[2];    /* Z - all polygon has same Z value. */
  313.  
  314.     V -> Pnext = AllocVertex(0, 0, NULL, V -> Pnext);
  315.     V = V -> Pnext;
  316.     PT_COPY(V -> Pt, Vnext -> Pt);
  317.     PT_CLEAR(V -> Normal);
  318.     }
  319.  
  320.     return V;
  321. }
  322.  
  323. /*****************************************************************************
  324. *   Convert the given closed loop list to polygons, and return them. the     *
  325. * original given polygon vertex list is freed, and the first loop is subst.  *
  326. * instead.                                     *
  327. *****************************************************************************/
  328. static void ClosedLoopsToPolys(InterSegListStruct *PClosed, PolygonStruct *Pl)
  329. {
  330.     int LoopNum = 0;
  331.     VertexStruct *V, *VHead;
  332.     InterSegmentStruct *PISeg, *PItemp;
  333.     InterSegListStruct *PClosedTemp;
  334.  
  335.     MyFree((char *) Pl -> V, ALLOC_VERTEX);
  336.     Pl -> Pnext = NULL;
  337.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  338.  
  339.     while (PClosed != NULL) {
  340.     /* Convert the InterList to vertex list and free the first: */
  341.     V = VHead = InterLoopToVrtxList(PClosed -> PISeg);
  342.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  343.         FatalError("ClosedLoopsToPolys: Closed loop with less than 3 vertices");
  344.  
  345.     PISeg = PClosed -> PISeg;      /* Time to free the InterSegmentList: */
  346.     while (PISeg != NULL) {
  347.         PItemp = PISeg;
  348.         PISeg = PISeg -> Pnext;
  349.         MyFree((char *) PItemp, ALLOC_OTHER);
  350.     }
  351.  
  352.     while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt */
  353.     MyFree((char *) V -> Pnext, ALLOC_VERTEX);/*and free - same as first.*/
  354.     V -> Pnext = VHead;               /* Make vertex list circular. */
  355.  
  356.     if (LoopNum++) {
  357.         Pl -> Pnext = AllocPolygon(0, 0, VHead, Pl -> Pnext);
  358.         PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane);
  359.     }
  360.     else {
  361.         Pl -> V = VHead;
  362.     }
  363.  
  364.     PClosedTemp = PClosed;
  365.     PClosed = PClosed -> Pnext;
  366.     MyFree((char *) PClosedTemp, ALLOC_OTHER);
  367.     }
  368. }
  369.  
  370. /*****************************************************************************
  371. *   This routines cuts the given polygon into its interior closed loops by   *
  372. * adding an edge from the polygon boundary to each of its closed loops.      *
  373. *   For example:                                 *
  374. *                                         *
  375. * +-----------------------+      +-----------------------+             *
  376. * |                       |     |                       |             *
  377. * |  / \         / \      |     |  / \________ / \      |             *
  378. * |  \ /        |   |     |     |  \ /        |   |_____|             *
  379. * |      _       \ /      | -->  |      _       \ /      |             *
  380. * |     / \_              | -->  |     / \_              |             *
  381. * |    |    |             |     |    |    |_____________|             *
  382. * |     \__/              |     |     \__/              |             *
  383. * |                       |      |                       |             *
  384. * +-----------------------+      +-----------------------+             *
  385. *                                         *
  386. *   Algorithm:                                     *
  387. * 1. Transform the polygon and the closed loops to a plane parallel to XY    *
  388. *    plane (Z = Const plane).                             *
  389. * 2. For each loop find its MaxX while keeping the information on the        *
  390. *    vertex on that extremum.                             *
  391. * 3. For the loop with the biggest MaxX:                     *
  392. *    3.1. Use that extremum vertex (which must be non concave corner) to     *
  393. *         test if loop is in the reverse direction the polygon itself is,    *
  394. *         and reverse it if not.                         *
  395. *    3.2. Fire a ray from the extremum vertex, to the +X direction outside   *
  396. *         of the loop till it intersect the polygon, break the polygon at    *
  397. *         that point and add two edges to beginning of loop from breaking    *
  398. *         point and from end of loop to breaking point (beginning/end point  *
  399. *      of loop is the extremum vertex point).                 *
  400. * 4. Repeat step 3, with all loops.                         *
  401. * 5. Transfrom the new polygon back (using the inverse matrix of step 1)     *
  402. *    to its original orientation.                         *
  403. *                                         *
  404. * Returns TRUE iff the original polygon boundary is in output.             *
  405. *                                         *
  406. *****************************************************************************/
  407. static int CombineClosedLoops(PolygonStruct *Pl, InterSegListStruct *PClosed,
  408.                                 int AinB)
  409. {
  410.     RealType MaxX;
  411.     PointType V1, V2, Normal, PlNormal;
  412.     MatrixType RotMat;
  413.     VertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct;
  414.     InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast,
  415.     *PClosedMaxXLast;
  416.     InterSegmentStruct *PISeg, *PItemp, *PISegMaxX;
  417.  
  418.     Pl -> Pnext = NULL;          /* Make sure this polygon is disconnected. */
  419.  
  420.     /* Stage 1 - Transform the vertices to a plane parallel to XY plane: */
  421.     GenRotateMatrix(RotMat, Pl -> Plane);
  422.     V = VHead = Pl -> V;
  423.     do {                    /* Transform the polygon itself. */
  424.     MatMultVecby4by4(V -> Pt, V -> Pt, RotMat);
  425.     V = V -> Pnext;
  426.     }
  427.     while (V != NULL && V != VHead);
  428.  
  429.     PClosedTemp = PClosed;
  430.     while (PClosedTemp != NULL) {        /* And transform the loops also. */
  431.     PISeg = PClosed -> PISeg;
  432.     while (PISeg != NULL) {
  433.         MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  434.         MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  435.  
  436.         PISeg = PISeg -> Pnext;
  437.     }
  438.  
  439.     PClosedTemp = PClosedTemp -> Pnext;
  440.     }
  441.     if (!MatInverseMatrix(RotMat, RotMat))     /* Find the inverse matrix. */
  442.     FatalError("CombineClosedLoops: Inverse matrix does not exists");
  443.  
  444.     /* Evalaute the normal to the polygon (which must be convex!). Note we   */
  445.     /* cannt simply use the Plane normal as the polygon was transformed.     */
  446.     V = Pl -> V;
  447.     do {
  448.     Vnext = V -> Pnext;
  449.     PT_SUB(V1, Vnext -> Pt, V -> Pt);
  450.     PT_SUB(V2, Vnext -> Pnext -> Pt, Vnext -> Pt);
  451.     VecCrossProd(PlNormal, V1, V2);
  452.     V = Vnext;
  453.     }
  454.     while (PT_LENGTH(PlNormal) < EPSILON);
  455.  
  456.     PClosedTemp = PClosed;
  457.     while (PClosedTemp != NULL) {
  458.     /* Stage 2 - find MaxX extremum value of given loop, test the loop   */
  459.     /* direction, and reverse it if wrong. Note we convert the loop      */
  460.     /* given as InterSegListStruct list into VertexStruct list first.    */
  461.     PISegMaxX = PISeg = PClosedTemp -> PISeg;
  462.     MaxX = PISeg -> PtSeg[0][0];          /* Get first vertex X val. */
  463.     PISeg = PISeg -> Pnext;
  464.     while (PISeg)
  465.     {
  466.         if (PISeg -> PtSeg[0][0] > MaxX) {
  467.         MaxX = PISeg -> PtSeg[0][0];
  468.         PISegMaxX = PISeg;
  469.         }
  470.         PISeg = PISeg -> Pnext;
  471.     }
  472.     PClosedTemp -> PISegMaxX = PISegMaxX;
  473.  
  474.     PClosedTemp = PClosedTemp -> Pnext;
  475.     }
  476.  
  477.     /* Stage 3/4 - find the loop with biggest MaxX and combine it with the   */
  478.     /* polygon itself. Do it for all closed loops, in list:             */
  479.     PClosedTemp = PClosed;
  480.     while (PClosed != NULL) {
  481.     /* Find the one with maximum MaxX, and delete it from PClosed list.  */
  482.     PClosedLast = PClosedMaxX = PClosedTemp = PClosed;
  483.     MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0];
  484.     while (PClosedTemp != NULL)
  485.     {
  486.         if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) {
  487.         PClosedMaxX = PClosedTemp;
  488.         PClosedMaxXLast = PClosedLast;
  489.         }
  490.         PClosedLast = PClosedTemp;
  491.         PClosedTemp = PClosedTemp -> Pnext;
  492.     }
  493.     if (PClosedMaxX == PClosed)
  494.         PClosed = PClosed -> Pnext;                    /* Del. from */
  495.     else
  496.         PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext; /* PClosed list.*/
  497.  
  498.     /* Create a vertex list from the loop: */
  499.     V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg);
  500.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  501.         FatalError("CombineClosedLoops: Closed loop with less than 3 vertices");
  502.  
  503.     V = VHead;
  504.     while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt */
  505.     MyFree((char *) V -> Pnext, ALLOC_VERTEX);/*and free - same as first.*/
  506.     V -> Pnext = VHead;               /* Make vertex list circular. */
  507.  
  508.     PISegMaxX = PClosedMaxX -> PISegMaxX;
  509.  
  510.     /* Now test if the vertex list should be reversed. Find the vertices */
  511.     /* which form the PISegMaxX segment, so V -> Pnext is the first      */
  512.         /* vertex in PISegMaxX segment. Then the 3 vertices V , V -> Pnext   */
  513.         /* (on PISegMaxX), V -> Pnext -> Pnext (on PISegMaxX), must form     */
  514.     /* convex corner which we use to test if loop needs to be reversed:  */
  515.     while (!PT_EQ(V -> Pnext -> Pt, PISegMaxX -> PtSeg[0]))
  516.             V = V -> Pnext;
  517.     VMaxX = V -> Pnext;
  518.     PT_COPY(VStruct.Pt, V -> Pt);  /* Prepare in point in REAL position. */
  519.     MatMultVecby4by4(VStruct.Pt, VStruct.Pt, RotMat);
  520.     VStruct.Pnext = NULL;
  521.     if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) {
  522.         /* The Inside of the object is actually the loop itself. In that */
  523.         /* case we simply return all the loops converted into polygon.   */
  524.         /* This case is simple...                         */
  525.         MyFree((char *) VHead, ALLOC_VERTEX);  /* Free loop vertex list. */
  526.         PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */
  527.         PClosedTemp = PClosed = PClosedMaxX;
  528.         while (PClosedTemp != NULL) {    /* Transform the loops back. */
  529.         PISeg = PClosed -> PISeg;
  530.         while (PISeg != NULL) {
  531.             MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  532.             MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  533.  
  534.             PISeg = PISeg -> Pnext;
  535.         }
  536.         PClosedTemp = PClosedTemp -> Pnext;
  537.         }
  538.  
  539.         ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/
  540.         return FALSE;       /* Boundary is NOT part of object result. */
  541.     }
  542.     PT_SUB(V1, VMaxX -> Pt, V -> Pt);
  543.     PT_SUB(V2, VMaxX -> Pnext -> Pt, VMaxX -> Pt);
  544.     VecCrossProd(Normal, V1, V2);
  545.     if (DOT_PROD(Normal, PlNormal) > 0) {        /* Need to reverse list. */
  546.         Vprev = VHead;
  547.         V = Vprev -> Pnext;
  548.         Vnext = V -> Pnext;
  549.         do {
  550.         V -> Pnext = Vprev;/* Reverse to point on prev instead next. */
  551.         Vprev = V;
  552.         V = Vnext;
  553.         Vnext = V -> Pnext;
  554.         }
  555.         while (Vprev != VHead);
  556.     }
  557.  
  558.     PISeg = PClosedMaxX -> PISeg;  /* Time to free the InterSegmentList: */
  559.     while (PISeg != NULL) {
  560.         PItemp = PISeg;
  561.         PISeg = PISeg -> Pnext;
  562.         MyFree((char *) PItemp, ALLOC_OTHER);
  563.     }
  564.     MyFree((char *) PClosedMaxX, ALLOC_OTHER);
  565.  
  566.     /* O.k. lets fire a ray from VMaxX to +X direction and see where it  */
  567.     /* intersects the polygon. The routine CutPolygonAtRay will add two  */
  568.     /* vertices at the ray intersection into polygon vertex list and     */
  569.     /* return a pointer to first one, so we can chain our loop directly  */
  570.     /* between these two new vertices.                     */
  571.     V = CutPolygonAtRay(Pl, VMaxX -> Pt);
  572.     Vnext = V -> Pnext;
  573.     /* Introduce a copy of VMaxX and successor to VMaxX: */
  574.     VMaxX -> Pnext = AllocVertex(VMaxX -> Count, VMaxX -> Tags, NULL,
  575.                                 VMaxX -> Pnext);
  576.     PT_COPY(VMaxX -> Pnext -> Pt, VMaxX -> Pt);
  577.     PT_CLEAR(VMaxX -> Pnext -> Normal);
  578.     V -> Pnext = VMaxX -> Pnext;
  579.     SET_INTERNAL_EDGE(V);
  580.     VMaxX -> Pnext = Vnext;
  581.     SET_INTERNAL_EDGE(VMaxX);
  582.     }
  583.  
  584.     /* Stage 5 - Time to rotate polygon back to its original position. */
  585.     V = VHead = Pl -> V;
  586.     do {
  587.     MatMultVecby4by4(V -> Pt, V -> Pt, RotMat);
  588.     V = V -> Pnext;
  589.     }
  590.     while (V != NULL && V != VHead);
  591.  
  592.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  593.     RST_CONVEX_POLY(Pl);         /* This polygon is not convex any more. */
  594.  
  595.     return TRUE;
  596. }
  597.  
  598. /*****************************************************************************
  599. *   Push on the adjacency stack, all adjacent polygons which are complete    *
  600. * (no intersection) and are adjacent to complete edges (originated from         *
  601. * input polygons) of the given polygon.                         *
  602. *****************************************************************************/
  603. static void PushAdjOnStack(PolygonStruct *Pl, PolygonStruct *AdjStack[],
  604.                              int *StackPointer)
  605. {
  606.     VertexStruct *V = Pl -> V;
  607.  
  608.     do {
  609.     /* If you wants to propagate iff both vertices are original then     */
  610.     /* uncomment the next line.                         */
  611.     if (IS_ORIGINAL_VRTX(V) /* && IS_ORIGINAL_VRTX(V -> Pnext) */
  612.         && V -> PAdj != NULL)
  613.         AdjStack[++*StackPointer] = V -> PAdj;
  614.     if (*StackPointer >= ADJ_STACK_SIZE) {
  615.         FatalError("Adjacency stack overflow, object too big\n");
  616.     }
  617.     V = V -> Pnext;
  618.     }
  619.     while (V != Pl -> V);
  620. }
  621.  
  622. /*****************************************************************************
  623. *   Chain two Polygon lists into one. For fast processing it is prefered the *
  624. * first one to be to shorter. Returns pointer to chained list.             *
  625. *****************************************************************************/
  626. static PolygonStruct *ChainPolyLists(PolygonStruct *Pl1, PolygonStruct *Pl2)
  627. {
  628.     PolygonStruct *Ptemp;
  629.  
  630.     if (Pl1 == NULL)
  631.         return Pl2;
  632.     else if (Pl2 == NULL)
  633.     return Pl1;
  634.     else {
  635.     Ptemp = Pl1;
  636.     while (Ptemp -> Pnext != NULL) Ptemp = Ptemp -> Pnext;
  637.     Ptemp -> Pnext = Pl2;
  638.     return Pl1;
  639.     }
  640. }
  641.  
  642. /*****************************************************************************
  643. *   This routine coordinates all the extraction of the polygons from the     *
  644. * intersecting lists. Does it in the following steps:                 *
  645. * 1. Mark all polygons with no intersection at all as complete polygons.     *
  646. *    (this is cause that this polygon will be totally in or out, according   *
  647. *    to inter-polygon adjacencies propagation...)                 *
  648. *    Also Mark them as undefined (if in output or undefined) yet.         *
  649. *    Uses PolygonStruct Tags to save these bits.                 *
  650. * 2. 2.1. Convert the unordered segment list of each polygon to closed loops *
  651. *         (if create a hole in polygon) or open (if crosses its boundary).   *
  652. *    2.2. Order the open loops along the perimeter of the polygon (note      *
  653. *      these loops cannt intersect. For example (5 vertices polygon):     *
  654. *             -----------------------------L3                 *
  655. *        |  ---------------L1  -----L2 |          --------L4   --L5   *
  656. *        | |               |  |     |  |         |        |   |  |    *
  657. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
  658. *         Note L1, L2 are enclosed in L3 loop, and that the order is circular*
  659. *    2.3. "Break" the polygon at each open loop that has no enclosed loops   *
  660. *      in it. For example we can start at L1, L2, L4, L5 and then L3.     *
  661. *      "Break" means - replace the vertex chain between the two loop end  *
  662. *      points, with the loops itself. Depends upon the relation required  *
  663. *      we may need to output a new polygon form from the deleted chain    *
  664. *      and that loop. In addition we may form a new polygon from last     *
  665. *      loop and was was left from the original polygon             *
  666. *      For each formed polygon, for each complete edge of it (i.e. edge   *
  667. *      which was originally in the polygon) test the adjacent polygon     *
  668. *      if it is complete (as marked in 1.) and if in or undefined (marked *
  669. *      undefined in 1.) is still undefined:                     *
  670. *      2.3.1. set it to be in.                         *
  671. *      2.3.2. push it on adjacency stack.                     *
  672. *    2.4. For each closed loop - find in which polygon (from polygons         *
  673. *      created in 2.3.) it is enclosed, and decompose it.             *
  674. * 3. While adjacencies stack not empty do:                     *
  675. *    3.1. pop top polygon from stack and output it.                 *
  676. *    3.2. For each of its edges (which obviousely must be complete edges)    *
  677. *      if adjacent polygon is complete and undefined:             *
  678. *      3.3.1. set it to be in.                         *
  679. *      3.3.2. push it on adjacency stack.                     *
  680. *    3.3  go back to 3.                                 *
  681. *                                         *
  682. *   The above algorithm defines in as in output, but dont be confused with   *
  683. * the required inter-object AinB (or AoutB if FALSE), which used to         *
  684. * determine which side of the trimming loop should be output.             *
  685. *   Note this routine may return non-convex polygons (but marked as so) even *
  686. * though the input for the booleans must be convex polygons only!         *
  687. *   In order to keep the given object unchanged, a whole new copy off the    *
  688. * polygon list is made. The polygons of the list that are not in the output  *
  689. * are freed: a global list of all polygons (pointers) is used to scan them   *
  690. * in the end and free the unused ones (list PolysPtr).                 *
  691. *****************************************************************************/
  692. ObjectStruct *ExtractPolygons(ObjectStruct *PObj, int AinB)
  693. {
  694.     int NumOfPolys = 0, StackPointer = -1;
  695.     PolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr, *OriginalPl,
  696.         *Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl;
  697.     VertexStruct *V, *Vnext;
  698.     InterSegListStruct *PClosed, *POpen, *Ptemp;
  699.  
  700. #ifdef DEBUG3
  701.     printf("Enter ExtractPolygons\n");
  702. #endif /* DEBUG3 */
  703.  
  704.     TestBooleanCtrlBrk();
  705.  
  706.     /* Stage 1. - mark all polygons as needed: */
  707.     PlHead = Pl = PObj -> U.Pl.P;
  708.     /* Gen. a copy of Pl, so we can modify the original polygon list: */
  709.     PObj -> U.Pl.P = CopyPolygonList(Pl);
  710.  
  711.     while (Pl != NULL) {
  712.     NumOfPolys++;         /* Count number of polygons in original object. */
  713.     if (Pl -> PAux != NULL) {     /* The intersection list is not empty! */
  714.         RST_COMPLETE_POLY(Pl);     /* Mark it as non complete polygon. */
  715.         V = Pl -> V;
  716.         do {
  717.         SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */
  718.         V = V -> Pnext;
  719.         }
  720.         while (V != Pl -> V);
  721.     }
  722.     else {
  723.         SET_COMPLETE_POLY(Pl);         /* Mark it as complete polygon. */
  724.         RST_INOUTPUT_POLY(Pl);     /* And as undefined (if in output). */
  725.         RST_ADJPUSHED_POLY(Pl);     /* And as not pushed on adj. stack. */
  726.     }
  727.     Pl = Pl -> Pnext;
  728.     }
  729.  
  730.     /* Stage 2. - scan the polygons and subdivide the intersecting ones: */
  731.     Pl = PlHead;
  732.  
  733.     /* We will save pointers to ALL polygons in list so we could free in the */
  734.     /* end the ones that are not in the output list, and therefore unused.   */
  735.     PolysPtr = (PolygonStruct **)
  736.         MyMalloc(sizeof(PolygonStruct *) * NumOfPolys, ALLOC_OTHER);
  737.     NumOfPolys = 0;
  738.  
  739.     while (Pl != NULL) {
  740.     TestBooleanCtrlBrk();
  741.  
  742.     PolysPtr[NumOfPolys++] = Pl;        /* Save pointer to this polygon. */
  743.  
  744.     PlNext = Pl -> Pnext;
  745.     Pl -> Pnext = NULL;
  746.  
  747.     if (!IS_COMPLETE_POLY(Pl)) {/* They are intersections with this one. */
  748.         /* Convert the intersecting segments into open/closed loops. */
  749.         LoopsFromInterList(Pl, &PClosed, &POpen);
  750.  
  751.         /* Save copy of original polygon vertex list as we need its      */
  752.         /* normals to interpolate for the internal ones.             */
  753.         OriginalPl = AllocPolygon(1, Pl -> Tags, CopyVList(Pl -> V), NULL);
  754.         PLANE_COPY(OriginalPl -> Plane, Pl -> Plane);
  755.  
  756.         if (POpen != NULL) {
  757.         /* Sort the Open loops into an order we can handle... */
  758.         SortOpenInterList(Pl, &POpen);
  759.         SplPl = NewPl = NULL;     /* Keep the list of split polygons. */
  760.  
  761.         while (POpen != NULL) {    /* Clip the open loops from polygon: */
  762.             /* Note ClipOpenLoopFromPoly also frees the InterSegment */
  763.             /* list pointed by POpen (but not POpen itself).          */
  764.             NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB);
  765.             if (NewPl != NULL) {   /* If loop clipped a new polygon, */
  766.             PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
  767.             NewPl -> Pnext = SplPl;/* add to split polygon list. */
  768.             SplPl = NewPl;
  769.             /* And push adj. polygons of complete edges on stack.*/
  770.             PushAdjOnStack(NewPl, AdjStack, &StackPointer);
  771.             }
  772.             Ptemp = POpen;
  773.             POpen = POpen -> Pnext;
  774.             MyFree((char *) Ptemp, ALLOC_OTHER);
  775.         }
  776.  
  777.         /* Last clip generated nothing (NewPl == NULL) so part that  */
  778.         /* left from Pl (PlCopy) is IN output list! Add this poly:   */
  779.         if (NewPl == NULL) {
  780.             PLANE_COPY(Pl -> Plane, OriginalPl -> Plane);
  781.             Pl -> Pnext = SplPl; /* And chain what was left from it. */
  782.             SplPl = Pl;
  783.             /* And push adjacent polygons of complete edges on stack.*/
  784.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  785.             SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */
  786.             RST_CONVEX_POLY(Pl);       /* May be not convex now. */
  787.         }
  788.  
  789.         UpdateVerticesNormals(SplPl, OriginalPl);
  790.         }
  791.         else
  792.         SplPl = Pl;
  793.  
  794.         if (PClosed != NULL) {
  795.         for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext)
  796.             Pl -> PAux = NULL;
  797.  
  798.         /* Classify the closed loops into the appropriate polygon. */
  799.         while (PClosed != NULL) {
  800.             Ptemp = PClosed -> Pnext;
  801.             for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
  802.             if (CGPolygonRayInter3D(Pl, PClosed -> PISeg -> PtSeg[0],
  803.                         0) % 2 == 1) {
  804.                 /* This closed loop is contained in this polygon.*/
  805.                 PClosed -> Pnext = (InterSegListStruct *) Pl -> PAux;
  806.                 Pl -> PAux = (VoidPtr) PClosed;
  807.                 break;
  808.             }
  809.             }
  810.             if (Pl == NULL) {
  811.             /* This closed loop is part of a trimmed out by open */
  812.             /* loop region. It should be only the island formed  */
  813.             /* by this closed loop then.                 */
  814.             /* Make a new polygon - a copy of the original and   */
  815.             /* Put this loop in it.                     */
  816.             NewPl = AllocPolygon(1, OriginalPl -> Tags,
  817.                          CopyVList(OriginalPl -> V), NULL);
  818.             PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
  819.             NewPl -> PAux = (VoidPtr) PClosed;
  820.             NewPl -> Pnext = SplPl;
  821.             SplPl = NewPl;
  822.             }
  823.             PClosed = Ptemp;
  824.         }
  825.  
  826.         for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
  827.             /* Make a "cut" from the loop(s)  +-------+    +-------+ */
  828.             /* to boundary if possible, and   |       |    |       | */
  829.             /* converting Pl to a nonconvex   |  / \  | -> |  / \__| */
  830.             /* polygon, that has an edge (the |  \ /  | -> |  \ /  | */
  831.             /* cut) which is shared twice in  |       |    |       | */
  832.             /* the same polygon              +-------+    +-------+ */
  833.             PClosed = (InterSegListStruct *) Pl -> PAux;
  834.             Pl -> PAux = NULL;
  835.             if (CombineClosedLoops(Pl, PClosed, AinB)) {
  836.             /* If returned with TRUE -  polygon boundary is in   */
  837.             /* output, so add all its neighbours to adj. stack.  */
  838.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  839.             }
  840.  
  841.             UpdateVerticesNormals(Pl, OriginalPl);
  842.         }
  843.         }
  844.  
  845.         OutputPl = ChainPolyLists(SplPl, OutputPl);
  846.  
  847.         /* Free the original polygon vertex list. */
  848.         MyFree((char *) OriginalPl, ALLOC_POLYGON);
  849.     }
  850.  
  851.     Pl = PlNext;
  852.     }
  853.  
  854.     /* Stage 3. - handling adjacencies and propagate them in polygons:         */
  855.     /* Pop off the elements from the stack, and propagate them using their   */
  856.     /* adjacencies.                                 */
  857.     while (StackPointer >= 0) {
  858.     Pl = AdjStack[StackPointer--];             /* Pop top element. */
  859.     if (!IS_COMPLETE_POLY(Pl) ||        /* Ignore non complete polygons. */
  860.          IS_INOUTPUT_POLY(Pl)) continue;          /* If already handled. */
  861.  
  862.     SET_INOUTPUT_POLY(Pl);      /* Mark this one as handled for next time. */
  863.  
  864.     V = Pl -> V;         /* Push all adjacent ones that not handled yet. */
  865.     do {
  866.         if (V -> PAdj &&
  867.         IS_COMPLETE_POLY(V -> PAdj) &&
  868.         !IS_INOUTPUT_POLY(V -> PAdj) &&
  869.         !IS_ADJPUSHED_POLY(V -> PAdj)) {
  870.         SET_ADJPUSHED_POLY(V -> PAdj);
  871.         AdjStack[++StackPointer] = V -> PAdj;   /* Push it on stack. */
  872.         if (StackPointer >= ADJ_STACK_SIZE)
  873.             FatalError("Adjacency stack overflow, object too big\n");
  874.         }
  875.         V = V -> Pnext;
  876.     }
  877.     while (V != Pl -> V);
  878.  
  879.     Pl -> Pnext = OutputPl;           /* And chain it into output list. */
  880.     OutputPl = Pl;
  881.     }
  882.  
  883.     /* Free all polygons which are not in the output list: */
  884.     while (--NumOfPolys >= 0) {
  885.     if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) {
  886.         PolysPtr[NumOfPolys] -> Pnext = NULL; /* Free only this polygon. */
  887.         MyFree((char *) (PolysPtr[NumOfPolys]), ALLOC_POLYGON);
  888.     }
  889.     }
  890.     MyFree((char *) PolysPtr, ALLOC_OTHER);
  891.  
  892.     /* Another floating point kludge: a polygon may have zero length edge so */
  893.     /* search for those and remove them - someone may die because of one...  */
  894.     Pl = OutputPl;
  895.     while (Pl != NULL) {
  896.     V = Pl -> V;
  897.     do {
  898.         Vnext = V -> Pnext;
  899.         if (PT_EQ(V -> Pt, Vnext -> Pt)) {
  900.         /* Ahh - we got you. Simply skip Vnext vertex and free it: */
  901.         V -> Pnext = Vnext -> Pnext;
  902.         /* Update polygon vertex pointer if point on freed vertex: */
  903.         if (Pl -> V == Vnext) Pl -> V = Vnext -> Pnext;
  904.         Vnext -> Pnext = NULL;              /* Dont free too much! */
  905.         MyFree((char *) Vnext, ALLOC_VERTEX);
  906.         Vnext = V -> Pnext;
  907.         }
  908.         V = Vnext;
  909.     }
  910.     while (V != Pl -> V && V != NULL);
  911.  
  912.     Pl = Pl -> Pnext;
  913.     }
  914.  
  915. #ifdef DEBUG3
  916.     printf("Exit ExtractPolygons\n");
  917. #endif /* DEBUG3 */
  918.  
  919.     return GenPolyObject("", OutputPl, NULL);     /* Return resulting object. */
  920. }
  921.  
  922. #ifdef DEBUG2
  923.  
  924. /*****************************************************************************
  925. *   Print the content of the given polygon, to standard output.             *
  926. *****************************************************************************/
  927. static void PrintVrtxList(VertexStruct *V)
  928. {
  929.     VertexStruct *VHead = V;
  930.  
  931.     do {
  932.     printf("    %12lf %12lf %12lf", V -> Pt[0], V -> Pt[1], V -> Pt[2]);
  933.     if (IS_INTERNAL_EDGE(V))
  934.         printf(" (Internal)\n");
  935.     else
  936.         printf("\n");
  937.     V = V -> Pnext;
  938.     }
  939.     while (V!= NULL && V != VHead);
  940. }
  941.  
  942. /*****************************************************************************
  943. *   Print the content of the given InterSegment list, to standard output.    *
  944. *****************************************************************************/
  945. static void PrintInterList(InterSegmentStruct *PInt)
  946. {
  947.     printf("INTER SEGMENT LIST:\n");
  948.  
  949.     if (PInt) printf("Entry vertex pointer %p\n", PInt -> V[0]);
  950.     while (PInt) {
  951.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  952.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  953.         FP_SEG(PInt->V[0]),
  954.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  955.         FP_SEG(PInt->V[1]));
  956.     if (PInt -> Pnext == NULL)
  957.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  958.  
  959.     PInt = PInt -> Pnext;
  960.     }
  961. }
  962.  
  963. #endif /* DEBUG2 */
  964.